/*
 * [18] 删除链表重复节点
 *
 * 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
 * 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
 *
 * g++ test_cpp.cpp -ggdb -std=c++11
 */

// @lc code=start

// 回顾普通的二分查找
/**
int binarysearch(vector<int>& a, int k) {
  int left = 0;
  int right = a.size() - 1;
  int mid;
  while (left <= right) {
    mid = (left + right) / 2;
    // k较a[mid]大时，在右半区间查找
    if (a[mid] < k) left = mid + 1;
    // k较a[mid]小时，在右半区间查找
    else if (a[mid] > k)
      right = mid - 1;
    // 若相等则返回mid
    else
      return mid;
  }
  // 找不到时返回-1
  return -1；
}
**/

#include <algorithm>
#include <iostream>
#include <stack>
#include <string>
#include <vector>

using namespace std;

struct ListNode
{
  int val;
  struct ListNode* pnext;
  ListNode(int x) : val(x), pnext(NULL) {}
};

class Solution
{
 public:
  /*
    ListNode* deleteDuplicates(ListNode* head) {
      if(head ==NULL) return NULL;
      ListNode* p;
      p = head;
      while(p)
      {
        if(p->next && p->next->val == p->val)
        {
          p->next=p->next->next;
          p=p->next->next; // 因为试图使用空指针，p->next->next有可能是个空指针，所以代码不能这样写
        }
        else
        {
          p=p->next;
        }
      }
      return head;
    }*/

  ListNode* deleteDuplicates(ListNode* head)
  {
    auto cur = head;
    while (cur)
    {
      if (cur->next && cur->next->val == cur->val) cur->next = cur->next->next;
      // 我的代码不同：通过if中cur->next避免访问空指针，统一在else中移动指针
      else
        cur = cur->next;
    }
    return head;
  }

  ListNode* deleteDuplication(ListNode* pHead)
  {
    if (pHead == NULL) return pHead;

    // 指向前面最晚访问过的不重复结点
    ListNode* pre = NULL;

    // 指向当前处理的结点
    ListNode* p = pHead;

    // 指向当前处理结点后面结点
    ListNode* q = NULL;

    while (p != NULL)
    {
      // 当前节点p,
      // 其实是p指向当前结点），与它下一个结点p->next的val相同，说明要删掉有这个val的所有结点
      if (p->pnext != NULL && p->pnext->val == p->val)
      {
        q = p->pnext;

        // 找到q,它指向最后一个与p_val相同的节点，那p到q(包含)都是要删除的
        while (q != NULL && q->pnext != NULL && q->pnext->val == p->val)
        {
          q = q->pnext;
        }
        // 如果p指向链表中第一个元素，p -> ... -> q ->... , 要删除p到q,
        // 将指向链表第一个元素的指针pHead指向q->next
        if (p == pHead)
        {
          pHead = q->pnext;
        }
        // //如果p不指向链表中第一个元素，pre -> p ->...->q ->... ，要删除p到q，即pre->next =
        // q->next
        else
        {
          pre->pnext = q->pnext;
        }
        // 当前处理的p要向链表尾部移动
        p = q->pnext;
      }
      else
      {
        pre = p;
        p = p->pnext;
      }
    }
    return pHead;
  }
};

int main()
{
  class Solution solute;
  ListNode* nodehead = new ListNode(-1);

  ListNode* node1 = new ListNode(1);
  nodehead->pnext = node1;

  ListNode* node2 = new ListNode(2);
  node1->pnext = node2;
  node2->pnext = nullptr;

  ListNode* node3 = new ListNode(2);
  node2->pnext = node3;
  node3->pnext = nullptr;

  ListNode* node4 = new ListNode(3);
  node3->pnext = node4;
  node4->pnext = nullptr;

  ListNode* head = solute.deleteDuplication(node1);

  return 0;
}

// @lc code=end
